<!DOCTYPE html>
<html lang="en">
  <head>
    <meta charset="UTF-8" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />
    <title>Document</title>
  </head>
  <body>
    <script>
      /* 背包问题，因为需要有序，所以是排列。因此外层背包，内层物品 */
      var wordBreak = function (s, wordDict) {
        let bagSize = s.length;
        let dp = new Array(bagSize + 1).fill(false);
        dp[0] = true;
        for (let j = 0; j <= bagSize; j++) {
          for (let i = 0; i < wordDict.length; i++) {
            if (j >= wordDict[i].length) {
              let temp = s.slice(j - wordDict[i].length, j);
              if (wordDict.includes(temp) && dp[j - wordDict[i].length]) {
                dp[j] = true;
              }
            }
          }
        }
        return dp[bagSize];
      };
    </script>
  </body>
</html>
